"""
适用于非负整数排序

代码解释：
1.** 确定最大位数 ：通过数组中的最大值计算需要处理的最大位数（如最大值 802 有 3 位，需处理个位、十位、百位）。
2. 初始化桶 ：创建 10 个空桶（对应数字 0-9），用于临时存储不同位上数字相同的元素。
3. 按位排序（LSD 策略）**：
    从最低位（个位）开始，依次处理更高位（十位、百位等）。
    对每一位，计算除数（10^digit）来提取当前位的数字（如digit=1时，除数为 10，通过(num//10)%10提取十位数字）。
    将元素按当前位数字分配到对应桶中，再按桶的顺序（0-9）收集元素，形成新的数组。
4.清空桶：每轮处理后清空桶，为下一位排序做准备。

算法特点：
时间复杂度：O(d*(n+r))，其中d为最大位数，n为元素个数，r为基数（此处r=10）。
空间复杂度：O(n+r)，主要用于存储桶。
稳定性：基数排序是稳定排序，适合对多关键字或位数固定的元素排序（如整数、字符串等）。


该实现严格遵循李春葆教材中基数排序的基本思想，通过最低位优先的方式，利用桶排序完成每一位的排序，最终得到整体有序的数组。


"""


def radix_sort(arr):
    if not arr:
        return arr

    # 确定数组中的最大值，以确定最大位数
    max_val = max(arr)
    # 计算最大位数（如123有3位）
    max_digits = len(str(max_val))

    # 初始化10个桶（0-9），每个桶存储对应位的数字
    buckets = [[] for _ in range(10)]

    # 从最低位（个位）到最高位依次排序
    for digit in range(max_digits):
        # 计算当前处理的位数的除数（10^digit）
        divisor = 10 ** digit

        # 将元素分配到对应桶中
        for num in arr:
            # 提取当前位的数字（如digit=0取个位，digit=1取十位）
            current_digit = (num // divisor) % 10
            buckets[current_digit].append(num)

        # 从桶中收集元素，形成新的数组
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
            bucket.clear()  # 清空桶，为下一轮做准备

    return arr


# 测试
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print("基数排序结果:", sorted_arr)  # 输出: [2, 24, 45, 66, 75, 90, 170, 802]

